package fun.codedesign.jdk.math.reverse;

import java.util.*;


public class Anagrams {
    /**
     * 高效的变位词查找算法
     * <p>给定一组单词，然后查找该组单词中属于某个单词(传入的)的变位词;
     * 将传入的单词List以算法签名作为HashMap的key来存储，大幅度的削减比对单词字母的时间
     */

    final Map<String, List<String>> lookup = new HashMap<>();

    /**
     * 时间复杂度 O(m) m为单词长度
     *
     * @param words
     */
    public Anagrams(List<String> words) {
        for (final String word : words) {
            // 单词字母重新排序作为key
            final String signature = alphabetize(word);
            if (lookup.containsKey(signature)) {
                lookup.get(signature).add(word);
            } else {
                // 匿名内部类的方式
                lookup.put(signature, new ArrayList<String>() {
                    {
                        add(word);
                    }
                });
            }
        }
    }

    private String alphabetize(final String word) {
        final byte[] bytes = word.getBytes();
        Arrays.sort(bytes);
        return new String(bytes);
    }

    /**
     * 从lookup中取得相对应的单词列表，否则为空列表
     *
     * @param word 单词
     * @return
     */
    public List<String> getAnagrams(final String word) {
        final String signature = alphabetize(word);
        return lookup.containsKey(signature) ? lookup.get(signature) : new ArrayList<String>();
    }
}
